//438.找到字符串中所有字母异位词

import java.util.ArrayList;
import java.util.List;


class Solution2 {
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<Integer>();

        //将字符串转换成字符数组
        char[] p = pp.toCharArray();
        char[] s = ss.toCharArray();
        
        int[] hash1 = new int[26];//统计字符串p中每一个字符出现的个数
        for(char ch : p){
            hash1[ch-'a']++;//ch-'a'求该字符对应的下标
        }
        int m = p.length;

        int[] hash2 = new int[26];//统计窗口中每个字符出现的个数
        int count = 0;
        int left = 0;
        int right = 0;
        
        for(right = 0;right < s.length;right++){
            char in = s[right];
            //进窗口+维护count
            if(++hash2[in - 'a'] <= hash1[in - 'a']){
                count++;
            }

            //判断
            if(right - left + 1 > m){
                char out = s[left];
                //出窗口+维护count
                if(hash2[out - 'a']-- <= hash1[out - 'a']){
                    count--;
                }
                left++;
            }

            //更新结果
            if(count == m){
                ret.add(left);
            }          
        }
        return ret;
    }
}